Recent articles such as Daniel Bernstein, Cache-timing attacks on AES, 2005, and Colin Percival, Cache Missing for Fun and Profit, 2005, and Dag Arne Osvik, Adi Shamir, Eran Tromer, Cache Attacks and Countermeasures: the Case of AES, 2005, and Joseph Bonneau, Ilya Mironov, Cache-Collision Timing Attacks Against AES, 2006, expose a potential security vulnerability that may affect systems running virtual machines. In short, in a scenario where multiple guest operating systems share a single or multiple processors which in turn share a memory bus, it may be possible for a malicious guest to discover the private key of one or more of the other guests.
This could be accomplished by 1. loading a cache with data, 2. causing the victim guest to run code that would populate memory in a certain way, and 3. subsequently attempting to retrieve the data loaded into the cache while measuring the time it takes to do so. By measuring the time it takes to retrieve data loaded into the cache, the malicious guest discovers whether such data is in fact still in the cache. If the data is not in the cache, it will take more time to retrieve. If the data is not in the cache, then it can be inferred that the victim guest used that cache location. By determining which cache locations were used by the victim guest, the malicious guest can learn something about the victim's operations, and potentially enough to compromise the security of the victim.
Existing recommended solutions to cache line cryptanalysis, as provided in the above cited references, suggest changing cryptographic algorithms to mask memory accesses. This has several limitations. First, it requires rewriting cryptographic algorithms which is a costly undertaking. Second, it assumes algorithms can be made analysis resistant. Third, rewriting algorithms could significantly impact their performance.
Other mitigations, such as isolating memory in an operating system to protect cryptographic processes, are potentially put at risk when run on a virtual machine. This is due to the fact that a virtualized guest operating system may not have control over how its memory has been allocated to it and how other memory has been allocated to other potentially hostile partitions.
Virtual machine technology is increasingly important in today's technological landscape. For instance, business models may emerge in which multiple guest operating systems are hosted by a commercial hosting service. Security threats cannot be tolerated in such a setting. The invention addresses the above described vulnerability, and also provides performance gains which may warrant use of the invention for non-security related purposes as well.